public class LinkedList {
    class ListNode{//这是内部节点
         public int val;
         public  ListNode next;//需要指向下一个节点，开辟一个指针。

        public ListNode(int val) {//这是构造方法
            this.val = val;
        }
    }
    public ListNode head;//没有初始化，默认是null.
    //头插
    public  void addFirst(int data){
        //创建一个数据域为data的节点
        ListNode node=new ListNode(data);
        node.next=head;
        head=node;
    }
    //尾插
    public  void addLast(int data){
        ListNode node=new ListNode(data);
        ListNode cur=head;
        if(head==null){
           head=node;
       }
        //找尾巴节点
       while(cur.next!=null){
           cur=cur.next;
       }
       //这时候cur已经是尾巴节点
        cur.next=node;

    }
    //任意位置插入----第一个数据节点为0下标
    public  void addIndex(int index,int data){
        ListNode node=new ListNode(data);
        //判断插入的位置是否合法
        if(index<0||index>size()){
            throw  new IndexWrongException("插入位置错误");
        }
        //这个要分情况而讨论
        //1.头插
        if(head==null){
            addFirst(data);
            return;
        }
        //2.尾插
        if(index==size()){
            addLast(data);
            return;
        }
        //3.中间插入
        ListNode cur=head;
        while(index>0){
            cur=cur.next;
            index--;
        }
        node.next=cur.next;
        cur.next=node;

    }
    //就单链表的长度
    public int size(){
        ListNode cur=head;
        int size=0;
        while (cur!=null){
            size++;
            cur=cur.next;
        }
        return size;
    }
    //删除第一次出现关键字的节点
    public  void remove(int key){
     //判断该链表是否为空
        if(isEmpty()){
            System.out.println("该单链表为空，无法删除");
        }
        //查找单链表中是否存在这个关键字
        ListNode flag=contains(key);
        if(flag==null){
            System.out.println("该单链表无此数");
            return;
        }
        flag.next=flag.next.next;
    }
    //判断单链表是否为空
    //true 空
    public boolean isEmpty(){
        return size()==0;
    }
    public  ListNode contains(int key){
        ListNode cur=head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
        }
            cur=cur.next;
        }
        return null;
    }
    //删除所有值为key的节点
    public  void removeAll(int key){
        //检查该单链表是否为空
        if(isEmpty()){
            System.out.println("此链表为空，无法删除");
        }
        ListNode cur=head.next;
        ListNode prev=head;
       while (cur!=null) {
           if (cur.val == key) {
               prev.next = cur.next;
               cur=cur.next;
           }else{
               prev=cur;
               cur=cur.next;
           }
        }
       if(head.val==key){
           head=head.next;
       }
    }

    public  void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
}
